package practice_2025_9.practice_9_26;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
    boolean[][] f;
    int len;

    /**
     * 分割回文串
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        // 将 s 分割成 多个子串，每个子串都是一个回文串 -> 所有分割方案
        len = s.length();
        s = " " + s;
        // f[i][j]: 以 i 为起始, j 为结尾的字符串是否是回文串
        f = new boolean[len + 1][len + 1];
        for(int i = len; i >= 0; i--) {
            for(int j = i; j <= len; j++) {
                if (i == j) {
                    f[i][j] = true;
                } else if (i + 1 == j && s.charAt(i) == s.charAt(j)) {
                    f[i][j] = true;
                } else if (s.charAt(i) == s.charAt(j)){
                    f[i][j] = f[i + 1][j - 1];
                }
            }
        }
        bfs(s, 1);
        return res;
    }
    public void bfs(String s, int begin) {
        // 递归出口
        if (begin > len) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = begin; i <= len; i++) {
            if (f[begin][i]) {
                // 继续递归
                // System.out.println(s.substring(begin, i + 1) + " begin: " + begin + " i+1: " + (i + 1));
                list.add(new String(s.substring(begin, i + 1)));
                bfs(s, i + 1);
                // 回溯
                list.remove(list.size() - 1);
            }
        }

    }

    /**
     * 最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        if(tLen > sLen) {
            return "";
        }
        // 返回 s 中涵盖 t 所有字符的最小子串
        Map<Character, Integer> hash = new HashMap<>();
        for(char ch: t.toCharArray()) {
            hash.put(ch, hash.getOrDefault(ch, 0) + 1);
        }

        int begin = 0, len = sLen + 1, count = 0;
        Map<Character, Integer> hash1 = new HashMap<>();
        for(int left = 0, right = 0; right < sLen; right++) {
            // System.out.println("left: " + left + " right: " + right);
            char in = s.charAt(right);
            hash1.put(in, hash1.getOrDefault(in, 0) + 1);
            // 当前是否是有效字符
            if (hash1.getOrDefault(in, 0) <= hash.getOrDefault(in, 0)) {
                count++;
            }
            // System.out.println("left: " + left + " right: " + right + " count: " + count);
            while(count >= tLen && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    begin = left;
                }
                char out = s.charAt(left);
                hash1.put(out, hash1.getOrDefault(out, 0) - 1);
                // 是否是合法字符
                if (hash1.getOrDefault(out, 0) < hash.getOrDefault(out, 0)) {
                    count--;
                }
                left++;
            }
        }
        // System.out.println("len: " + len);
        if (len > sLen) {
            return "";
        }
        return s.substring(begin, begin + len);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minWindow("ADOBECODEBANC", "ABC");
    }
}